package thired.class16_manacher;

import java.util.Arrays;

public class Class02_AddShortestEnd {
    public static String shortestEnd(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        char[] str = manacherString(s);
        int[] pArr = new int[str.length];
        int c = -1;
        int R = -1;
        for (int i = 0; i < str.length; i++) {
            pArr[i] = R > i ? Math.min(pArr[2*c-i],R - i) : 1;
            while (i + pArr[i] < str.length && i - pArr[i] > -1){
                if(str[i + pArr[i]] == str[i - pArr[i]]){
                    pArr[i]++;
                }else{
                    break;
                }
            }
            if(i + pArr[i] > R){
                R  = i + pArr[i];
                c = i;
            }
            if(R == str.length){
                break;
            }
        }
        return  reverse( s.substring(0,c/2 - (pArr[c]-1)/2));
    }

    private static char[] manacherString(String s) {
        char[] str = new char[s.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i < str.length; i++) {
            str[i] = (i & 1) == 0 ? '#' : s.charAt(index++);
        }
        return str;
    }
    public static String reverse(String str){
        char[] s1 = str.toCharArray();
        char[] res = new char[s1.length];
        for (int i = 0; i < s1.length; i++) {
            res[s1.length - i - 1] = s1[i];
        }
        return Arrays.toString(res);
    }
    public static void main(String[] args) {
        String str1 = "abcd123321dc";
        System.out.println(shortestEnd(str1));
    }
}

